Perm

Time Limit: 10 Sec Memory Limit: 256 MB

Description

很久以前，有一个 1~n的排列。
　　这个排列太杂乱无章了，方老师想要让它变得单调一些。
　　方老师打算把排列中的数划分成两个非空子序列，一个单调上升，一个单调下降。
　　需要注意的是，排列中的每个数必须恰在一个子序列中并保持原来在排列中的相对顺序不变。
　　由于方案可能会比较多，你只需要输出方案数 mod 666623333。

Input

第一行一个整数 n。
　　第二行 n 个 1~n 的整数，为一个 1~n 的排列。

Output

一个整数，满足题意的方案数 mod 666623333。

Sample Input

3
　　1 3 2

Sample Output

3

HINT

1 <= n <= 10^6

Solution

显然，我们运用DP。

我们记 f[i][j] 为做到了第 i 个数，i 为递增子序列结尾，j 为递减子序列结尾的方案数，g[i][j] 为做到了第 i 个数，i 为递减子序列结尾，j 为递增子序列结尾的方案数。

我们考虑 第 i 个数 和 第 i-1 个数 是否同属一个子序列：
　　　　如果同属一个子序列，那么 f[i][j] += f[i-1][j]（a[i-1] < a[i]），g[i][j] += g[i-1][j]（a[i-1] > a[i]）；（这里的 += 等价于 =）
　　　　如果不同属一个子序列，那么 f[i][i-1] += g[i-1][j]（a[j] < a[i]），g[i][i-1] += f[i-1][j]（a[j] > a[i]）。

我们考虑是否优化这个暴力。运用树状数组。

省掉第一维。如果 a[i-1] < a[i]，我们清空g，否则我们清空f。这个过程相当于完成了同属一个子序列的转移。

在转移之前记录接下来我们记S1为a[j] < a[i]的g[j]的和，记S2为a[j] > a[i]的f[j]的和。那么不同属一个的转移相当于f[i-1] += S1, g[i-1]+=S2。

初值显然就是f[n + 1] = 1, g[0] = 1（为了方便起见，BearChild把它设成f[n] = 1, g[1] = 1，在求和的时候求<=的和）

最后求一下f、g的和即可。注意考虑全为上升的或者全为下降的，若是如此，则答案-1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 1e6 + 5;

int n;
int a[ONE];
int Ans;

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

struct BIT
{
    int C[ONE], mark[ONE], Time_cnt;

    BIT()
    {
        Time_cnt = 0;
        memset(C, 0, sizeof(C));
        memset(mark, 0, sizeof(mark));
    }

    void Clear() {Time_cnt++;}
    int lowbit(int x) {return x & -x;}

    void Check(int x)
    {
        if(mark[x] != Time_cnt)
            C[x] = 0, mark[x] = Time_cnt;
    }

    void Add(int R, int x)
    {
        for(int i = R; i <= n; i += lowbit(i))
            Check(i), C[i] += x;
    }

    int Query(int R)
    {
        if(R == 0) return 0;
        int res = 0;
        for(int i = R; i >= 1; i -= lowbit(i))
            Check(i), res += C[i];
        return res;
    }
}F, G;

int main()
{
    n = get();
    for(int i = 1; i <= n; i++) a[i] = get();

    int PD;
    PD = -1; for(int i = 2; i <= n; i++) if(a[i - 1] > a[i]) {PD = 0; break;} Ans += PD;
    PD = -1; for(int i = 2; i <= n; i++) if(a[i - 1] < a[i]) {PD = 0; break;} Ans += PD;

    F.Add(n, 1);    G.Add(1, 1);
    for(int i = 2; i <= n; i++)
    {
        int S1 = G.Query(a[i]);
        int S2 = F.Query(n) - F.Query(a[i] - 1);
        if(a[i - 1] < a[i]) G.Clear();
        if(a[i - 1] > a[i]) F.Clear();
        F.Add(a[i - 1], S1), G.Add(a[i - 1], S2);
    }

    Ans += F.Query(n) + G.Query(n);

    printf("%d", Ans);
}